package com.my.leetcode;

import javafx.scene.layout.Priority;
import scala.Int;

import java.util.*;

public class DFSProblems {


    public static void main(String[] args) {


        TreeNode node = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(11);
        TreeNode node5 = new TreeNode(13);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(2);
        TreeNode node9 = new TreeNode(1);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
        node4.left = node7;
        node4.right = node8;
        node6.right = node9;

        DFSProblems dfsProblems = new DFSProblems();

        int [][] A = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
       // System.out.println(dfsProblems.numEnclaves(A));

       /* String s = "aaa";
        List<List<String>> res = dfsProblems.partition(s);
        System.out.println("res=======" + res.size());
        System.out.println("res=====" + res);
        System.out.println(dfsProblems.partition("aba"));
        System.out.println(dfsProblems.partition("aab"));*/


        int [] nums = {1,2,2};
        System.out.println(dfsProblems.subsets(nums));
    }


    /**
     * @author zlx
     * @Description 1306. 跳跃游戏 III
     * 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
     *
     * 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
     *
     * 注意，不管是什么情况下，你都无法跳到数组之外。
     *
     *
     *
     * 示例 1：
     *
     * 输入：arr = [4,2,3,0,3,1,2], start = 5
     * 输出：true
     * 解释：
     * 到达值为 0 的下标 3 有以下可能方案：
     * 下标 5 -> 下标 4 -> 下标 1 -> 下标 3
     * 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
     * 示例 2：
     *
     * 输入：arr = [4,2,3,0,3,1,2], start = 0
     * 输出：true
     * 解释：
     * 到达值为 0 的下标 3 有以下可能方案：
     * 下标 0 -> 下标 4 -> 下标 1 -> 下标 3
     * 示例 3：
     *
     * 输入：arr = [3,0,2,1,2], start = 2
     * 输出：false
     * 解释：无法到达值为 0 的下标 1 处。
     *
     *
     * 提示：
     *
     * 1 <= arr.length <= 5 * 10^4
     * 0 <= arr[i] < arr.length
     * 0 <= start < arr.length
     * @Date 4/19/21
     * @Param [arr, start]
     * @return boolean
     **/
    public boolean canReach(int[] arr, int start) {
        if(arr.length <= 0){
            return true;
        }
        boolean []visited = new boolean[arr.length];
        return canReachDfs(arr, start, visited);
    }


    public boolean canReachDfs(int [] arr, int start, boolean[] visited){

        if(start < 0 || start >= arr.length){
            return false;
        }

        if(arr[start] == 0){
            return true;
        }

        if(visited[start]){
            return false;
        }else{
            visited[start] = true;
        }

        return canReachDfs(arr, start - arr[start], visited) || canReachDfs(arr, start + arr[start], visited);
    }

    /**
     * @author zlx
     * @Description 131. 分割回文串 middle
     * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
     *
     * 返回 s 所有可能的分割方案。
     *
     * 示例:
     *
     * 输入: "aab"
     * 输出:
     * [
     *   ["aa","b"],
     *   ["a","a","b"]
     * ]
     * @Date 2020-12-14
     * @Param [s]
     * @return java.util.List<java.util.List<java.lang.String>>
     **/
    public List<List<String>> partition(String s) {
        rows = new ArrayList<>();
        row = new ArrayList<>();
        dfsPalindrome(s, 0);
        return rows;
    }


    public List<List<String>> rows = new ArrayList<>();
    public void dfsPalindrome(String s, int index){

        if(index >= s.length() && !row.isEmpty()){
            List<String> tmp = new ArrayList<>();
            if(!rows.contains(row)){
                tmp = new ArrayList<>(row);
                rows.add(tmp);
            }
        }

        if(index >= s.length()){
            return ;
        }

        for(int z = s.length();z >= 1;z--) {
            if(index + z > s.length()){
                continue;
            }
            if (isPalindrome(s, index, z)) {
                row.add(s.substring(index, index + z));
                dfsPalindrome(s, index+z);
                row.remove(row.size() - 1);
            } else {
               continue;
            }
        }

    }

    public boolean isPalindrome(String s, int start, int r){

        int end = start + r - 1;
        if(start >= s.length() || end >= s.length()){
            return false;
        }
        while (start < end){

            if(s.charAt(start) != s.charAt(end)){
                return false;
            }else{
                start++;
                end --;
            }
        }
        return true;
    }

    private void dfs(String s, int start, List<String> path) {
        if (start == s.length()) {
            rows.add(new ArrayList<>(path));
            return;
        }
        for (int i=start; i<s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                path.add(s.substring(start, i+1));
                dfs(s, i+1, path);
                path.remove(path.size()-1);
            } else if (i == s.length()-1) {
                return;
            }
        }
    }
    
    

    /**
     * @author zlx
     * @Description 1020. 飞地的数量 middle
     * 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。
     *
     * 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
     *
     * 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
     * 输出：3
     * 解释：
     * 有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
     * 示例 2：
     *
     * 输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
     * 输出：0
     * 解释：
     * 所有 1 都在边界上或可以到达边界。
     *
     *
     * 提示：
     *
     * 1 <= A.length <= 500
     * 1 <= A[i].length <= 500
     * 0 <= A[i][j] <= 1
     * 所有行的大小都相同
     * @Date 2020-11-26
     * @Param [A]
     * @return int
     **/
    public int numEnclaves(int[][] A) {

        if(A.length == 1 || A[0].length == 1){
            return 0;
        }

        int m = A.length;
        int n = A[0].length;
        for(int j = 0;j < n;j++){
            if(A[0][j] == 1){
                dfsEncalves(A, 0, j, m, n);
            }
        }


        for(int j = 0;j < n;j++){
            if(A[m-1][j] == 1){
                dfsEncalves(A, m-1, j, m, n);
            }
        }


        for(int i = 0;i < m;i++){
            if(A[i][0] == 1){
                dfsEncalves(A,  i, 0, m, n);
            }
        }

        for(int i = 0;i < m;i++){
            if(A[i][n-1] == 1){
                dfsEncalves(A,  i, n-1, m, n);
            }
        }

        int count = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(A[i][j] == 1){
                    count++;
                }
            }
        }


        return count;
    }

    int [][] directions = {{0,1}, {1, 0}, {0,-1}, {-1, 0}};

    public void dfsEncalves(int [][] A, int x, int y, int m, int n){

        if(x < 0 || x >=m || y < 0 || y >= n || A[x][y] == 0){
            return ;
        }
        A[x][y] = 0;
        dfsEncalves(A, x, y+1, m, n);
        dfsEncalves(A, x, y-1, m, n);
        dfsEncalves(A, x+1, y, m, n);
        dfsEncalves(A, x-1, y, m, n);

    }



    public List<Integer> subSet = new ArrayList<>();

    public List<List<Integer>> subSets = new ArrayList<>();


    /**
     * @author zlx
     * @Description 78. 子集 middle
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     *
     * 说明：解集不能包含重复的子集。
     *
     * 示例:
     *
     * 输入: nums = [1,2,3]
     * 输出:
     * [
     *   [3],
     *   [1],
     *   [2],
     *   [1,2,3],
     *   [1,3],
     *   [2,3],
     *   [1,2],
     *   []
     * ]
     * @Date 2020-09-21
     * @Param [nums]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> subsets(int[] nums) {

        subSet = new ArrayList<>();
        subSets = new ArrayList<>();
        dfsSubSets(nums, 0);
        return subSets;
    }


    public void dfsSubSets(int [] nums, int index){

        subSets.add(new ArrayList<>(subSet));
        if(subSet.size() >= nums.length){
            return;
        }
        for(int i = index;i < nums.length;i++) {
            subSet.add(nums[i]);
            dfsSubSets(nums, i+1);
            subSet.remove(subSet.size() - 1);
        }
    }


    /**
     * @author zlx
     * @Descriptio 47. 全排列 II  middle
     * 给定一个可包含重复数字的序列，返回所有不重复的全排列。
     *
     * 示例:
     *
     * 输入: [1,1,2]
     * 输出:
     * [
     *   [1,1,2],
     *   [1,2,1],
     *   [2,1,1]
     * ]
     * @Date 2020-09-18
     * @Param [nums]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums == null || nums.length <= 0){
            return null;
        }

        permutes = new ArrayList<>();
        onePermute = new ArrayList<>();

        boolean [] flag = new boolean[nums.length];
        //解法I dfs+List判断是否重复
        dfsGenerateUniquePermute(nums, flag);
        //解法II dfs+剪纸
//        Arrays.sort(nums);
//        dfsGenerateUniquePermuteII(nums, flag);
        return permutes;
    }

    // 解法I dfs+List判断是否重复
    public void dfsGenerateUniquePermute(int [] nums, boolean[] flag){

        if(onePermute.size() == nums.length){
            List<Integer> tmp = new ArrayList<>(onePermute);
            //判断是否存在重复排列
            if(!permutes.contains(tmp)) {
                permutes.add(new ArrayList<>(onePermute));
            }
            return ;
        }

        for(int i = 0;i < nums.length;i++){
            if(!flag[i]){
                onePermute.add(nums[i]);
                flag[i] = true;
                dfsGenerateUniquePermute(nums, flag);
                flag[i]= false;
                onePermute.remove(onePermute.size() - 1);
            }
        }
    }

    // 解法I dfs+剪枝 效率更高
    public void dfsGenerateUniquePermuteII(int [] nums, boolean[] flag){

        if(onePermute.size() == nums.length){
            permutes.add(new ArrayList<>(onePermute));
            return ;
        }

        for(int i = 0;i < nums.length;i++){
            if(!flag[i]){
                //判断是否重复
                if(i > 0 && nums[i] == nums[i-1] && !flag[i-1]){
                    continue;
                }
                onePermute.add(nums[i]);
                flag[i] = true;
                dfsGenerateUniquePermuteII(nums, flag);
                flag[i]= false;
                onePermute.remove(onePermute.size() - 1);
            }
        }
    }

    public List<List<Integer>> permutes = new ArrayList<>();

    public List<Integer> onePermute = new ArrayList<>();

    /**
     * @author zlx
     * @Description 46. 全排列 middle
     * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     *
     * 示例:
     *
     * 输入: [1,2,3]
     * 输出:
     * [
     *   [1,2,3],
     *   [1,3,2],
     *   [2,1,3],
     *   [2,3,1],
     *   [3,1,2],
     *   [3,2,1]
     * ]
     * @Date 2020-09-18
     * @Param [nums]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> permute(int[] nums) {

        if(nums == null || nums.length <= 0){
            return null;
        }

        permutes = new ArrayList<>();
        onePermute = new ArrayList<>();

        boolean [] flag = new boolean[nums.length];
        dfsGeneratePermute(nums, flag);
        return permutes;
    }


    public void dfsGeneratePermute(int [] nums, boolean[] flag){

        if(onePermute.size() == nums.length){
            permutes.add(new ArrayList<>(onePermute));
            return ;
        }

        for(int i = 0;i < nums.length;i++){
            if(!flag[i]){
                onePermute.add(nums[i]);
                flag[i] = true;
                dfsGeneratePermute(nums, flag);
                flag[i]= false;
                onePermute.remove(onePermute.size() - 1);
            }
        }

    }



    private boolean [][] lines = new boolean[9][9];
    private boolean [][] columns = new boolean[9][9];
    private boolean [][][] blocks = new boolean[3][3][9];
    private List<int[]> blacks = new ArrayList<>();

    private boolean isResult = false;
    /**
     * @author zlx
     * @Description 37. 解数独 hard
     * 编写一个程序，通过已填充的空格来解决数独问题。
     *
     * 一个数独的解法需遵循如下规则：
     *
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     * 空白格用 '.' 表示。
     *
     *
     *
     * 一个数独。
     *
     *
     *
     * 答案被标成红色。
     *
     * Note:
     *
     * 给定的数独序列只包含数字 1-9 和字符 '.' 。
     * 你可以假设给定的数独只有唯一解。
     * 给定数独永远是 9x9 形式的。
     *
     *
     * 解题思路： 基于dfs进行求解，  boolean lines[i][j] 表示第i行 j+1 是否存在（j：0到8），存在为true
     *                           boolean columns[i][j] 表示第i列， j+1 是否存在（j：0到8）存在为true
     *                           boolean blocks[i/3][j/3][z] 表示第几个3*3块是否存在 z+1的 字符， 存在为true
     * @Date 2020-09-15
     * @Param [board]
     * @return void
     **/
    public void solveSudoku(char[][] board) {


        int m = board.length;
        int n = board[0].length;
        columns = new boolean[9][9];
        lines = new boolean[9][9];
        blocks = new boolean[3][3][9];
        blacks = new ArrayList<>();
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(board[i][j] == '.') {
                    blacks.add(new int[]{i, j});
                }else{
                    lines[i][board[i][j] - '0' - 1] = true;
                    columns[j][board[i][j] - '0' - 1] = true;
                    blocks[i / 3][j / 3][board[i][j] - '0' - 1] = true;
                }
            }
        }
        System.out.println("=============" + blacks.size());
        dfsShudu(board, 0);
    }


    public void dfsShudu(char[][] board, int index){

        if(blacks.size() == index){
            isResult = true;
            return ;
        }

        int [] pos = blacks.get(index);
        int tmpX = pos[0];
        int tmpY = pos[1];
        for(int i = 1;i <= 9 && !isResult;i++){
            if(!lines[tmpX][i-1] && !columns[tmpY][i-1] && !blocks[tmpX / 3][tmpY / 3][i - 1]){
                lines[tmpX][i-1] = columns[tmpY][i-1] = blocks[tmpX / 3][tmpY / 3][i-1] = true;
                board[tmpX][tmpY] = String.valueOf(i).toCharArray()[0];
                dfsShudu(board, index + 1);
                lines[tmpX][i-1] = columns[tmpY][i-1] = blocks[tmpX/3][tmpY / 3][i-1] = false;
            }
        }
    }



    /**
     * @author zlx
     * @Description 332. 重新安排行程 middle
     * 给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
     *
     * 说明:
     *
     * 如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
     * 所有的机场都用三个大写字母表示（机场代码）。
     * 假定所有机票至少存在一种合理的行程。
     * 示例 1:
     *
     * 输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
     * 输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
     * 示例 2:
     *
     * 输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
     * 输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
     * 解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
     * @Date 2020-08-31
     * @Param [tickets]
     * @return java.util.List<java.lang.String>
     **/
    Map<String, PriorityQueue<String>> map = new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        map = new HashMap<>();
        iterationList = new ArrayList<>();
        for(List<String> ticket : tickets){

            String from = ticket.get(0);
            String to = ticket.get(1);

            if(!map.containsKey(from)){
                map.put(from, new PriorityQueue<>());
            }
            map.get(from).offer(to);
        }
        System.out.println("findItinrary :" + map);
        iterationList = new ArrayList<>();
        dfsIteration("JFK");
        return iterationList;
    }

    public static List<String> iterationList = new ArrayList<>();

    public void dfsIteration(String key){
        if(key == null){
            return ;
        }
        iterationList.add(key);
        if(!map.containsKey(key)){
            return ;
        }
        PriorityQueue<String> queue = map.get(key);
        dfsIteration(queue.poll());
    }

    public void dfs(Map<String, PriorityQueue<String>> map, String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(map, curr);
        }
        iterationList.add(curr);
    }



    public List<String> findItineraryII(List<List<String>> tickets) {
        map = new HashMap<>();
        iterationList = new ArrayList<>();
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if (!map.containsKey(src)) {
                map.put(src, new PriorityQueue<String>());
            }
            map.get(src).offer(dst);
        }
        System.out.println("findItinrary II:" + map);
        dfs("JFK");
        Collections.reverse(iterationList);
        return iterationList;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        iterationList.add(curr);
    }





    /**
     * @author zlx
     * @Description 17. 电话号码的字母组合  middle
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
     *
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     *
     *
     *
     * 示例:
     *
     * 输入："23"
     * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
     *
     * 解题思路： 基于DFS进行求解
     * @Date 2020-08-26
     * @Param [digits]
     * @return java.util.List<java.lang.String>
     **/
    public List<String> letterCombinations(String digits) {

        if(digits == null || digits.length() <= 0){
            return new ArrayList();
        }

        Map<Integer, String> map = new HashMap<>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "suv");
        map.put(9, "wxyz");

        letterRes = new ArrayList<>();
        row = new ArrayList<>();
        dfsLetterComninationsII(digits, 0 , map, "");

        return letterRes;
    }


    public List<String> letterRes = new ArrayList<>();
    public List<String> row = new ArrayList<>();

    //dfs求解方法1
    public void dfsLetterComninations(String digits, int index, Map<Integer, String> map){

        if(row.size() == digits.length()){
            String tmp = "";
            for(String i : row){
                tmp += i;
            }
            letterRes.add(tmp);
            return;
        }

        int digit = digits.charAt(index) - '0';
        String str = map.get(digit);

        for(int i = 0;i < str.length();i++){
            row.add(String.valueOf(str.charAt(i)));
            dfsLetterComninations(digits, index+1, map);
            row.remove(row.size() - 1);
        }

    }

    //dfs求解方法II
    public void dfsLetterComninationsII(String digits, int index, Map<Integer, String> map, String tmpRes){

        if(tmpRes.length() == digits.length()){

            letterRes.add(tmpRes);
            return;
        }

        int digit = digits.charAt(index) - '0';
        String str = map.get(digit);

        for(int i = 0;i < str.length();i++){
            dfsLetterComninationsII(digits, index+1, map, tmpRes + String.valueOf(str.charAt(i)));
        }

    }


    /**
     * @author zlx
     * @Description 130. 被围绕的区域 middle
     * 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
     *
     * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     *
     * 示例:
     *
     * X X X X
     * X O O X
     * X X O X
     * X O X X
     * 运行你的函数后，矩阵变为：
     *
     * X X X X
     * X X X X
     * X X X X
     * X O X X
     *
     *解释:
     *
     * 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。
     * 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
     *
     * 解题思路： 从边界的O出发，找到和边界O相邻的O结点，标记为A，表示没有被X包围；
     *
     * @Date 2020-08-11
     * @Param [board]
     * @return void
     **/
    public void solve(char[][] board) {

        if(board == null || board.length == 0 || board.length <=2 || board[0].length <= 2){
            return ;
        }
        int m = board.length;
        int n = board[0].length;
        int [][] directions = {{0,1}, {1,0}, {0, -1}, {-1, 0}};

        for(int j = 0;j <n;j++){
            dfsSolve(board, 0, j);
            dfsSolve(board, m-1, j);
        }

        for(int i = 0;i < m;i++){
            dfsSolve(board, i, 0);
            dfsSolve(board, i, n-1);
        }

        for(int i =0;i < m;i++){
            for(int j = 0;j < n;j++){

                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }


    public void dfsSolve(char[][] board, int x, int y){

        if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O'){
            return ;
        }

        board[x][y] = 'A';
        dfsSolve(board, x, y+1);
        dfsSolve(board, x+1, y);
        dfsSolve(board, x, y-1);
        dfsSolve(board, x-1, y);
    }






    /**
     * @author zlx
     * @Description 841. 钥匙和房间   middle
     *
     * 有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
     *
     * 在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
     *
     * 最初，除 0 号房间外的其余所有房间都被锁住。
     *
     * 你可以自由地在房间之间来回走动。
     *
     * 如果能进入每个房间返回 true，否则返回 false。
     *
     * 示例 1：
     *
     * 输入: [[1],[2],[3],[]]
     * 输出: true
     * 解释:
     * 我们从 0 号房间开始，拿到钥匙 1。
     * 之后我们去 1 号房间，拿到钥匙 2。
     * 然后我们去 2 号房间，拿到钥匙 3。
     * 最后我们去了 3 号房间。
     * 由于我们能够进入每个房间，我们返回 true。
     * 示例 2：
     *
     * 输入：[[1,3],[3,0,1],[2],[0]]
     * 输出：false
     * 解释：我们不能进入 2 号房间。
     *
     *
     * 解题思路； 基于dfs求解，有一个注意点：你可以自由地在房间之间来回走动。
     * 官方解题思路： 基于Stack完成dfs
     *
     * @Date 2020-07-24
     * @Param [rooms]
     * @return boolean
     **/
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        System.out.println(rooms.size());
        if(rooms == null || rooms.size() <= 1){
            return true;
        }
        if(rooms.get(0).size() <= 0){
            return false;
        }
        boolean [] flag = new boolean[rooms.size()];
        flag[0] = true;
        List<Integer> keys = rooms.get(0);
        for(Integer key : keys){
            flag[key] = true;
            if(dfsRooms(rooms, key, flag) || isVisitAll(flag)){
                return true;
            }
        }
        return false;

    }

    public boolean dfsRooms(List<List<Integer>> rooms, int keyIndex, boolean [] flag){

        List<Integer> myRooms = rooms.get(keyIndex);
        if(myRooms.size() <= 0){
            return isVisitAll(flag);
        }

        for(Integer tmpKey : myRooms){
            if(flag[tmpKey]){
                if(isVisitAll(flag))
                    return true;
                continue;
            }
            flag[tmpKey] = true;
            if(dfsRooms(rooms, tmpKey, flag)){
                return true;
            }
        }
        return false;
    }


    public boolean isVisitAll(boolean [] flags){
        for(boolean flag : flags){
            if(!flag){
                return false;
            }
        }
        return true;
    }

    /**
     * medium
     * 547. 朋友圈
     * 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
     *
     * 给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
     *
     * 示例 1:
     *
     * 输入:
     * [[1,1,0],
     *  [1,1,0],
     *  [0,0,1]]
     * 输出: 2
     * 说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
     * 第2个学生自己在一个朋友圈。所以返回2。
     * 示例 2:
     *
     * 输入:
     * [[1,1,0],
     *  [1,1,1],
     *  [0,1,1]]
     * 输出: 1
     * 说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
     *
     * 解题思路： 这是一个对角矩阵，A[i][j] = A[j][i], 深度优先遍历， i->j是朋友， 只要继续找j的朋友，早找j的朋友的朋友
     * 和 【200. 岛屿数量】 有区别，朋友圈是传递关系， 岛屿数量是独立关系
     * @param M
     * @return
     */
    public int findCircleNum(int[][] M) {

        if(M == null || M.length == 0){
            return 0;
        }
        boolean [][] flag = new boolean[M.length][M[0].length];
        int count = 0;
        for(int i =0;i < M.length;i++){
            for(int j = 0;j < M[0].length;j++){
                if(M[i][j] == 1 && !flag[i][j]){
                    count++;
                    flag[i][j] = true;
                    flag[j][i] = true;
                    dfsFindCircleNums(M, flag, j);
                }

            }
        }
        return count;
    }


    public void dfsFindCircleNums(int [][] M, boolean[][] flag, int indexX){

        for(int j = 0; j < M[0].length;j++){
            if(indexX == j){
                flag[indexX][j] = true;
                continue;
            }else{
                if(M[indexX][j] == 1 && !flag[indexX][j]){

                    flag[indexX][j] = true;
                    flag[j][indexX] = true;
                    dfsFindCircleNums(M, flag, j);
                }
            }
        }
    }



    /**
     * 638. 大礼包
     * medium
     * 在LeetCode商店中， 有许多在售的物品。
     *
     * 然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
     *
     * 现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
     *
     * 每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
     *
     * 任意大礼包可无限次购买。
     *
     * 示例 1:
     *
     * 输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
     * 输出: 14
     * 解释:
     * 有A和B两种物品，价格分别为¥2和¥5。
     * 大礼包1，你可以以¥5的价格购买3A和0B。
     * 大礼包2， 你可以以¥10的价格购买1A和2B。
     * 你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。
     * 示例 2:
     *
     * 输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
     * 输出: 11
     * 解释:
     * A，B，C的价格分别为¥2，¥3，¥4.
     * 你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
     * 你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
     * 你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
     * 说明:
     *
     * 最多6种物品， 100种大礼包。
     * 每种物品，你最多只需要购买6个。
     * 你不可以购买超出待购清单的物品，即使更便宜。
     * @param price
     * @param special
     * @param needs
     * @return
     */
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return helper(price, needs, special, 0);
    }


    public int helper(List<Integer> price, List<Integer> needs, List<List<Integer>> special, int pos){

        int local_min = getPrices(needs, price);
        for(int i = pos;i < special.size();i++){
            List<Integer> promotion = special.get(i);
            List<Integer> tmp = new ArrayList<>();
            for(int j = 0; j < needs.size();j++){
                if(promotion.get(j) > needs.get(j)){
                    tmp = null;
                    break;
                }else{
                    tmp.add(needs.get(j) - promotion.get(j));
                }
            }
            if(tmp != null){
                local_min = Math.min(local_min, promotion.get(promotion.size() - 1) + helper(price, tmp, special, i));
            }
        }
        return local_min;
    }


    public int getPrices(List<Integer> needs, List<Integer> prices){

        int res = 0;
        for(int i = 0;i < needs.size();i++){
            res += needs.get(i) * prices.get(i);
        }
        return res;

    }


    /**
     *
     * 112. 路径总和 easy
     * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例: 
     * 给定如下二叉树，以及目标和 sum = 22，
     *
     *               5
     *              / \
     *             4   8
     *            /   / \
     *           11  13  4
     *          /  \      \
     *         7    2      1
     * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/path-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param root
     * @param sum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {


        res = false;
        dfsTree(root, sum, 0);
        return res;
    }


    boolean res = false;

    public void dfsTree(TreeNode node, int sum, int tempSum){

        if(node == null){
            return;
        }
        tempSum += node.val;
        System.out.println("tempSum is:-----------" + tempSum);
        if(tempSum == sum && node.left == null && node.right == null){
            res = true;
        }
        dfsTree(node.left, sum, tempSum);
        dfsTree(node.right, sum, tempSum);
    }
}
